#include <stdio.h>
//#include <malloc.h>
#include "stdlib.h"
#define MAXSIZE 10

//用二叉链表来表示一个二叉树
//1.创建二叉链表的结点结构体
typedef char ElementType;
//typedef struct node BTnode;
typedef struct node{
    //1.数据项
    ElementType data;
    //2.地址项，两个分别指向左右子树的指针
    struct node *left;
    struct node *right;
}BTNode;

//2.创建一个结点，并存储数据
/*
 * 函数名：createBTNode()
 * 输入：待存储的数据
 * 输出：返回创建好的结点
 * */
BTNode *createBTNode(ElementType data){
    //1.创建结点
    BTNode *node =malloc(sizeof(BTNode));

    //2.存储值
    node->data=data;
    node->left=NULL;
    node->right=NULL;

    return node;

}
//中序遍历
/*遍历过程：
（1）中序遍历左子树
（2）访问根节点
（3）中序遍历右子树*/
/*
 * 函数名：inOrder
 * 输入：树（其实是树的根节点）
 * 输出：没有输出
 * */

void inOrder(BTNode *root){
    if(root){
        //遍历过程：
        //（1）中序遍历左子树
        inOrder(root->left);
        //（2）访问根节点
        printf("%c ",root->data);
        //（3）中序遍历右子树
        inOrder(root->right);
    }
}

void preOrder(BTNode *root){
    if(root){
        //遍历过程：
        //（1）访问根节点
        printf("%c ",root->data);
        //（2）前序遍历左子树
        preOrder(root->left);
        //（3）前序遍历右子树
        preOrder(root->right);
    }
}

void postOrder(BTNode *root){
    if(root){
        //遍历过程：
        //（1）后序遍历左子树
        postOrder(root->left);
        //（2）后序遍历右子树
        postOrder(root->right);
        //（3）访问根节点
        printf("%c ",root->data);
    }
}

typedef struct queue Queue;
typedef BTNode* ElementType2;
struct queue{
    ElementType2 data[MAXSIZE];
    int front,rear;
};
/*Queue *createQueue(){
    Queue *queue= malloc(sizeof (Queue));
    queue->front=0;
    queue->rear=0;
    return queue; }
void EnQueue(Queue *queue,ElementType2 data){
    if((queue->rear+1)%MAXSIZE==queue->front){
        return;
    }
    queue->data[queue->rear]=data;
    queue->rear=(queue->rear+1)%MAXSIZE; }
ElementType2 DelQueue(Queue *queue){
    if(queue->front==queue->rear)
        return NULL;
    ElementType2 tmp=queue->data[queue->front];
    queue->front=(queue->front+1)%MAXSIZE;
    return tmp; }
int IsEmpty(Queue *queue){
    return queue->front==queue->rear;
}
void levelOrder(BTNode *root)
{
    if(root==NULL)
        return;
    //1.创建队列
   Queue *queue =  createQueue();
//2.根结点进队列
    EnQueue(queue,root);
    BTNode *tmp;
    while(!IsEmpty(queue))
    {
        tmp = DelQueue(queue);//出队
        //打印
        printf("%c ",tmp->data);
        //若存在左子节点，左结点进队
        if(tmp->left){
            EnQueue(queue,tmp->left);
        }
        //若存在右子节点，右子结点进队
        if(tmp->right){
            EnQueue(queue,tmp->right);
        }
    }
}*/

//根据扩展树的前序遍历创建一个二叉树
/*
 * 函数名：creatBT()
 * 输入：无 需要的参数在函数里面通过scanf()来获取
 * 输出：返回创建的树（其实是创建好的二叉结点） 返回值类型就是二叉结点 BTnode
 * */
BTNode *creatBt(){
    //1.创建结点
    BTNode *root;
    //1.1 通过scanf()来获取准备存到树结点里面的值
    ElementType str;
    scanf("%c",&str);
    //1.2 将获取的值存到对应的结点
    if(str=='#'){//1.2.1
        root =NULL;
    } else{
        //该结点存在，我们需要将获取的值存放到创建好的结点里面
        //1.2.2 给结点分配空间
        root = malloc(sizeof(BTNode));
        //1.2.3 给结点赋值
        root->data=str;//数据项
        root->left= creatBt();
        root->right=creatBt();
    }
    //2.返回结点
    return  root;
}


void levelOrder(BTNode *root)
{
    if(root==NULL)
        return;
    //1.创建队列
    //1.定义了一个数组
    BTNode *data[1000];
    int front=0;
    int rear = 0;
//2.根结点进队列
    data[rear++]=root;
    BTNode *tmp;
    while(front!=rear)
    {
        //出队
        tmp=data[front++];
        //打印
        printf("%c ",tmp->data);
        //若存在左子节点，左结点进队
        if(tmp->left){
            data[rear++]=tmp->left;
        }
        //若存在右子节点，右子结点进队
        if(tmp->right){
            // EnQueue(queue,tmp->right);
            data[rear++]=tmp->right;
        }
    }
}

//求树的高度
/*
 * 树的高度height=Max[左子树的高度left,右子树的高度]+1
 * 函数名：getHeight()
 * 输入：树(树的根结点)
 * 输出：树的高度 数值类型 int
 *
 * */
int getHeight(BTNode *root){
    //1.树为空
    if(root =NULL)
        return 0;
    //树的高度height=Max[左子树的高度left,右子树的高度]+1
    else{
        int leftHeight = getHeight(root->left);
        int rightHeight = getHeight(root->right);
        if(leftHeight>rightHeight)
            return leftHeight+1;
        else
            return rightHeight+1;
      //  return 1+(leftHeight>rightHeight?leftHeight:rightHeight);

    }
}
//求叶子结点的数量
/*
 *
 * 用递归的思想来实现求叶子结点的数量
 * f(root)=f(f.left)+f(f.right)
 * 叶子结点：node.left==node.right==NULL
 *
 * 函数名：leaf_count()
 * 输入：树（根）
 * 输出：叶子的数量 int
 * */
int leaf_count(BTNode *root){
    //1.树为空
    if(root ==NULL)
        return 0;
    if(root->left=NULL&&root->right==NULL)
        return 1;
   return leaf_count(root->left)+ leaf_count(root->right);
}


int main() {
    //1.创建6个结点并存储对应的数据
    BTNode *nodeA= createBTNode('A');
    BTNode *nodeB= createBTNode('B');
    BTNode *nodeD= createBTNode('D');
    BTNode *nodeF= createBTNode('F');
    BTNode *nodeI= createBTNode('I');
    BTNode *nodeL= createBTNode('L');

    //2.将结点连接成树
    nodeA->left=nodeB;
    nodeA->right=nodeD;
    nodeB->right=nodeF;
    nodeF->left=nodeL;
    nodeD->left=nodeI;

    inOrder(nodeA);
    printf("\n");
    preOrder(nodeA);
    printf("\n");
    postOrder(nodeA);
    // AB#FL###DI###
    printf("测试层序遍历:\n");
    levelOrder(nodeA);
    //printf("Hello, World!\n");
    return 0;
}
